package L614;

/**
 * @program: javase
 * @description: 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * @author: luolidong
 * @create: 2021-06-14 19:56
 * @version: 1.0
 */
public class TrappingRainWater42 {
    public int trap(int[] height) {
        int len=height.length;
//    从左往右，记录左边最大值
        int[] leftHeight=new int[len];
        leftHeight[0]=height[0];
        for (int i = 1; i < len; i++) {
            leftHeight[i]=Math.max(height[i],leftHeight[i-1]);
        }
        //    从右往左，记录右边最大值
        int[] rightHeight=new int[len];
        rightHeight[len-1]=height[len-1];
        for (int i = len-2; i >=0 ; i--) {
            rightHeight[i]=Math.max(height[i],rightHeight[i+1]);
        }

//        用最小值-高度
        int res=0;
        for (int i=0;i<len;i++){
            res+=Math.min(leftHeight[i],rightHeight[i])-height[i];
        }
        return res;
    }


}
